\section{Parcours en largeur}

La distance en largeur entre deux nœuds Soient u et v deux nœuds. On appelle occurrences d’un noeud n, O(n) l’ensemble des positions des hyperliens pointant vers n
dans les textes des autres nœuds. 
La distance en largeur entre u et v, notée L(u, v), est définie par :

    L (u, v) = min $\{$k $|$ u $\epsilon$ V$_k$ (v)$\}$ \\
 où 

V$_k$ (v) = $\{$w $|$ $\exists$ p$_v$ $\epsilon$ O(v), $\exists$ p$_w$
$\epsilon$ O(w), $|$p$_v$ - p$_w$ $\leq|$ k$\}$

Pour ce faire, nous récupérons à l'aide de la fonction {\tt wiki\_text} les pages qui contiennent le mot que nous recherchons et nous compactons son contenu comme décrit ci-dessous:
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.65]{images/compact.png} 
  \caption{Compression d'une page WikiPédia}
  \label{compact}
\end{figure}

Ensuite nous parsons deux fois cette structure pour récupérer les différents liens répondant à la requête de départ.
Nous allons donc en premier lieu récupérer tous les liens qui répondent à la requête suggérée et qui sont sur la gauche du lien de la requête.
L'algorithme est le suivant: on additionne les distances entre les liens, tout en ajoutant ces liens à une file temporaire, jusqu'à ce qu'on trouve le lien de la requête. Et si cette somme dépasse la distance donnée dans la requête, on enlève les premiers éléments ajoutés à la file en soustrayant leurs distances, jusqu'à ce que la somme des distances soit de nouveau inférieure à la distance de la requête.
Si nous trouvons le lien correspondant à la requête, nous ajoutons le contenu de la file temporaire dans l'ensemble de résultat, et nous mettons la somme à 0.
Voici un exemple de cet algorithme:
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.55]{images/struct-requete.png} 
  \label{compact}
\end{figure}

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.55]{images/gauche1.png} 
  \label{compact}
\end{figure}

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.55]{images/gauche2.png} 
  \label{compact}
\end{figure}
\clearpage
Ensuite, une fois toute la structure parcourue, nous la reparcourons une seconde fois pour récupérer les liens répondant à la requête donnée qui se trouvent à droite du lien de la requête.
Nous parcourons donc tout d'abord toute la liste jusqu'au premier lien correspondant à celui de la requète, et nous ajoutons à une file temporaire chaque lien trouvé et la distance qui le précède, et nous faisons la somme des distances rencontrées.
Si la distance dépasse celle donnée dans la requête, nous n'ajoutons pas le lien qui suit la dernière distance ajoutée, et nous arrêtons de compter jusqu'à ce que nous retrouvons de nouveau un lien correspondant à celui de la requête.
Si nous retrouvons ce lien, nous ajoutons les liens de la file temporaire dans l'ensemble de résultat, et nous remettons la somme à 0.
Et nous utilisons toujours l'ensemble des résultats obtenus après l'application du premier algorithme. Voici donc le second passage pour la même structure que précédemment:
\begin{figure}[!h]
  \center
  \includegraphics[scale=0.55]{images/droite.png} 
  \label{compact}
\end{figure}

Lorsqu'on arrive à la fin, nous ajoutant le contenu de la file temporaire à l'ensemble des résultats, et nous renvoyons cette ensemble.
Voici le résultat finale pour notre exemple:

\begin{figure}[!h]
  \center
  \includegraphics[scale=0.45]{images/resultat.png} 
  \label{compact}
\end{figure}

Pour un lien donné, nous appliquons ces deux algorithmes à la suite sur toutes les pages contenant le lien recherché, et nous faisons l'union de tous les ensembles de résultats trouvés.
